package com.example.josephu;

/**
 * @Author: wanqian
 * @Date: 2021/1/26 14:05
 */
public class CircleSingleLinkedList {

    private LinkedNode first;

    public LinkedNode getFirst() {
        return first;
    }

    public void setFirst(LinkedNode first) {
        this.first = first;
    }

    public CircleSingleLinkedList(int num) {
        if (num < 2) {
            throw new RuntimeException("无效数字");
        }

        LinkedNode pre = null;
        for (int i = 1; i <= num; i++) {
            LinkedNode linkedNode = new LinkedNode(i);
            if (i == 1) {
                this.first = linkedNode;
            } else {
                linkedNode.setNext(first);
                pre.setNext(linkedNode);
            }
            pre = linkedNode;
        }
    }

    public void list() {
        LinkedNode temp = this.first;
        do {
            System.out.println(temp);
            temp = temp.getNext();
        } while (temp != first);
    }

    public int length() {
        LinkedNode temp = this.first;
        int num = 0;
        do {
            num++;
            temp = temp.getNext();
        } while (temp != first);
        return num;
    }

    public void josephu(int start, int interval) {
        //省略校验过程

        LinkedNode pre = this.first;
        //将pre移动到最后末尾节点
        while (pre.getNext() != first) {
            pre = pre.getNext();
        }

        //根据起始位置位移start - 1步，此时处在起始节点前一个节点
        for (int i = 0; i < start - 1; i++) {
            pre = pre.getNext();
        }

        //是否只剩最后一个节点
        while (pre != pre.getNext()) {
            //开始报数，向前移动interval - 1步，此时处在带出列节点前一个节点
            for (int i = 0; i < interval - 1; i++) {
                pre = pre.getNext();
            }
            System.out.println(String.format("id=%d节点出列", pre.getNext().getId()));
            pre.setNext(pre.getNext().getNext());
        }
        System.out.println(String.format("id=%d节点出列", pre.getId()));
    }
}
